// Copyright (C) 2010 and onwards Noam Shazeer and Georges Harik
// Pieces of this code may be licenced under the Apache License, version 2.0 
//   from Harik Shazeer Labs

#ifndef _INTERPRET_H_
#define _INTERPRET_H_
#include <vector>
#include <set>
#include "util.h"
#include "thing.h"
#include "allocator.h"
#include "objects.h"
#include "nolock.h"
#include "timer.h"

#define ALL_NATIVES				\
  _NATIVE(INT_CHAR)			        \
  _NATIVE(TO_INT)				\
  _NATIVE(TO_DOUBLE)				\
  _NATIVE2(PLUS,+)				\
  _NATIVE2(MINUS,-)				\
  _NATIVE2(TIMES,*)				\
  _NATIVE(MOD)					\
  _NATIVE2(DIVIDE,/)				\
  _NATIVE2(EQUAL,=)				\
  _NATIVE2(LESS,<)				\
  _NATIVE(NOT)					\
  _NATIVE(TOSTRING)				\
  _NATIVE(TOSYMBOL)				\
  _NATIVE(ACCESSCOUNT)				\
  _NATIVE(FUNCALL)				\
  _NATIVE(APPLY)				\
  _NATIVE(HLESS)				\
  _NATIVE(HASH)					\
  _NATIVE(WEAK_REF)				\
  _NATIVE(WEAK_DEREF)				\
  _NATIVE(MLN)					\
  _NATIVE(LN)					\
  _NATIVE(EXP)					\
  _NATIVE(SORT)					\
  _NATIVE(ARRAY)				\
  _NATIVE(MARRAY)				\
  _NATIVE(GETTYPE)				\
  _NATIVE(ARRAYP)				\
  _NATIVE(MUTABLEP)				\
  _NATIVE(TOKENP)				\
  _NATIVE(CHARP)				\
  _NATIVE(INTEGERP)				\
  _NATIVE(SYMBOLP)				\
  _NATIVE(NATIVEP)				\
  _NATIVE(SPECIALP)				\
  _NATIVE(GLOBALP)				\
  _NATIVE(AREF)					\
  _NATIVE(MSET)					\
  _NATIVE(SET)                                  \
  _NATIVE(CAR)					\
  _NATIVE(CDR)					\
  _NATIVE(CONS)					\
  _NATIVE(PROGN)				\
  _NATIVE(LENGTH)				\
  _NATIVE(NODECOUNT)				\
  _NATIVE(RANDOM)				\
  _NATIVE(PRINT)				\
  _NATIVE(PRINTSTRING)				\
  _NATIVE(CRASH)				\
  _NATIVE(THROW)				\
  _NATIVE(RESIZE)				\
  _NATIVE(RG)					\
  _NATIVE(GETLIMIT)				\
  _NATIVE(GAMBLE)				\
  _NATIVE(GLOBALIZE)				\
  _NATIVE(HASH_SET)				\
  _NATIVE(HASH_DELETE)				\
  _NATIVE(HASH_LOOK)				\
  _NATIVE(GETMODE)                              \
   
#define _NATIVE(name) extern Thing name;
#define _NATIVE2(cname, lispname) extern Thing cname;
ALL_NATIVES
#undef _NATIVE
#undef _NATIVE2

enum NativeFunction {
#define _NATIVE(name) NATIVE_##name,
#define _NATIVE2(cname, lispname) NATIVE_##cname,
ALL_NATIVES
#undef _NATIVE
#undef _NATIVE2
};

#define ALL_SPECIAL				\
  _SPECIAL(NIL)					\
  _SPECIAL(T)					\
  _SPECIAL(IF)					\
  _SPECIAL(AND)					\
  _SPECIAL(OR)					\
  _SPECIAL(QUOTE)				\
  _SPECIAL(LIMIT)				\
  _SPECIAL(NOLIMIT)				\
  _SPECIAL(DOTIMES)				\
  _SPECIAL(REPEAT)				\
  _SPECIAL(ERROR)				\
  _SPECIAL(LAMBDA)				\
  _SPECIAL(LET)					\
  _SPECIAL(COMMA)				\
  _SPECIAL(BACKQUOTE)				\
  _SPECIAL(FORGET)				\
  _SPECIAL(DEBUG)				\
  _SPECIAL(CATCH)				\
  _SPECIAL(SAFEEXECUTE)				\
  _SPECIAL(DEF)					\
  _SPECIAL(CLOSURE)				\
  _SPECIAL(LOAD)				\
  _SPECIAL(BREAK)				\
  _SPECIAL(HIGHBITS)				\
  _SPECIAL(LOWBITS)				\
  _SPECIAL(SYSTEM_NODEBUG)			\

enum Special {
#define _SPECIAL(name) SPECIAL_##name,
  ALL_SPECIAL
#undef _SPECIAL
};

#define _SPECIAL(name) extern Thing name;
  ALL_SPECIAL;
#undef _SPECIAL

#define ALL_OPS					\
  _OP(PRINT_OP)				        \
  _OP(PRINT_STRING_OP)                          \
  _OP(PUSH_THING_OP)				\
  _OP(POP_OP)					\
  _OP(TO_INT_OP)				\
  _OP(TO_DOUBLE_OP)				\
  _OP(INT_CHAR_OP)				\
  _OP(PLUS_OP)					\
  _OP(TIMES_OP)					\
  _OP(CONST_PLUS_OP)				\
  _OP(CONST_TIMES_OP)				\
  _OP(CONST_EQUAL_OP)				\
  _OP(MOD_OP)					\
  _OP(DIVIDE_OP)				\
  _OP(MINUS_OP)					\
  _OP(EQUAL_OP)					\
  _OP(LESS_THAN_OP)				\
  _OP(NOT_OP)					\
  _OP(TOSTRING_OP)				\
  _OP(TOSYMBOL_OP)				\
  _OP(S_OP)					\
  _OP(DEBUG_VAR_INTRO_OP)			\
  _OP(DEBUG_VAR_REMOVE_OP)			\
  _OP(JUMP_OP)					\
  _OP(TEST_JUMP_OP)				\
  _OP(AND_OP)					\
  _OP(OR_OP)					\
  _OP(PUSH_HANDLER_OP)				\
  _OP(CRASH_OP)					\
  _OP(THROW_OP)					\
  _OP(RESIZE_OP)				\
  _OP(RG_OP)					\
  _OP(POP_HANDLER_OP)				\
  _OP(GETLIMIT_OP)				\
  _OP(TIME_OP)					\
  _OP(FORGET_OP)				\
  _OP(START_DOTIMES_OP)				\
  _OP(NEXT_DOTIMES_OP)				\
  _OP(FUNCALL_OP)				\
  _OP(APPLY_OP)					\
  _OP(SYSCALL_OP)				\
  _OP(HLESS_OP)					\
  _OP(HASH_OP)					\
  _OP(WEAK_REF_OP)				\
  _OP(WEAK_DEREF_OP)				\
  _OP(MLN_OP)					\
  _OP(LN_OP)					\
  _OP(EXP_OP)					\
  _OP(SORT_OP)					\
  _OP(CLEAN_FRAME_OP)				\
  _OP(ARRAY_OP)					\
  _OP(MARRAY_OP)				\
  _OP(GETTYPE_OP)				\
  _OP(ARRAYP_OP)				\
  _OP(MUTABLEP_OP)				\
  _OP(TOKENP_OP)				\
  _OP(CHARP_OP)					\
  _OP(INTEGERP_OP)				\
  _OP(SYMBOLP_OP)				\
  _OP(NATIVEP_OP)				\
  _OP(SPECIALP_OP)				\
  _OP(GLOBALP_OP)				\
  _OP(AREF_OP)					\
  _OP(CONST_AREF_OP)				\
  _OP(MSET_OP)					\
  _OP(SET_OP)                                   \
  _OP(LENGTH_OP)				\
  _OP(NODECOUNT_OP)				\
  _OP(RANDOM_OP)				\
  _OP(RETURN_OP)				\
  _OP(EXIT_OP)					\
  _OP(DEF_OP)					\
  _OP(READ_GLOBAL_OP)				\
  _OP(ACCESSCOUNT_OP)				\
  _OP(NOOP_OP)                                  \
  _OP(GLOBALIZE_OP)				\
  _OP(HASH_SET_OP)			      	\
  _OP(HASH_DELETE_OP)				\
  _OP(HASH_LOOK_OP)				\
  _OP(GETMODE_OP)                               \

enum OpCodes {
#define _OP(name) name,
ALL_OPS
#undef _OP
};

// modes are uint64s with one bit set.  
// permissions are ORs of modes. 
const uint64 kNoSystemMode = 0x1ull;
const uint64 kEconomyMode = 0x2ull;
const uint64 kGenerativeMode = 0x4ull;

void SetSyscallPermissions(uint64 call, uint64 permissions);

void InitUnboxedThings();

// Returns an empty string for failure or end of input
string ReadToken(istream &input);

// take "abc" -> lisp string "abc"
Thing CStringToThingString(ThreadAllocator *a, char * cstr);

// Conversion into things
Thing ToThing(ThreadAllocator *a_, string s);

// Outputing a thing in a way it can be read back in
ostream & operator << (ostream & ostr, Thing p);

// Read a thing from a stream
Thing ReadThing(ThreadAllocator *a_, istream &input);

// Expanding a backquoted thing into its interpretation
Thing ExpandBackquote(ThreadAllocator *a_, Thing root);

inline Thing ThingLessThan(Thing a, Thing b) {
  if (a.IsInteger() && b.IsInteger()) 
    return (a.GetInteger() < b.GetInteger()) ? T : NIL;
  if (a.IsNumber() && b.IsNumber()) 
    return (a.GetDouble() < b.GetDouble()) ? T : NIL;
  return NULL;
}


// References into the marray that code compiles into
enum CodeInfo {
  JUNK0,
  ARITY,
  JUNK1,
  COMPILE_LOG,
  CODE_INFO_MAX,
};

// We add a new code stack frame on non-inlined function calls
// Allows us to access the function and return from the function
struct CodeStackFrame {
  const Thing * return_ip_; // where we return when we are done.
  uint64 cache_key_; // if we will be caching the execution - where? 
  Thing cached_value_; // for verification 
  Thing compiled_code_; // the compiled code we're running
  int64 start_function_uncachable_count_;
  // points to the running function.  Parameters follow.  
  Thing * function_in_stack_; 
};

// A state of the interpreter that we can roll back to
// assuming the underlying stacks have not shrunk
struct InterpreterState {
  uint64 mode_;
  const Thing * ip_;
  Thing * stack_top_;
  Thing * debug_stack_top_;
  CodeStackFrame *code_stack_top_;
  uint64 array_stack_size_;
  // New runs of safe execute each get their own run_global_
  Thing run_global_;
};

// Specifies how to react to time limit and other exceptions
struct HandlerFrame {
  // If this frame matches, return to this state
  InterpreterState return_state_;
  
  // Used to know if you've blown a clock limit
  int64 clock_limit_;

  // A single or an array of exceptions this frame addresses
  // ALL catches all exceptions
  Thing exceptions_;

  // either LIMIT, CATCH, DEBUG, or SAFEEXECUTE
  // LIMIT frames are placed by (limit ...) commands
  // CATCH frames catch exceptions, return NIL and continue running
  // DEBUG frames stop the program and print debugging information
  // SAFEEXECUTE frames are placed upon each new safeexecute
  //    because handling shouldn't cross safeexecute boundaries
  //    and SafeExecute has some locals that need to be destroyed
  Thing type_;  

  // Can this frame handle this exception
  bool ExceptionMatches(Thing x) {
    if (exceptions_ == ALL) return true;
    if (x == exceptions_) return true;
    if (exceptions_.IsArray())
      for (uint64 i=0; i<exceptions_.ArraySize(); i++) 
	if (exceptions_.Ref(i) == x) return true;
    return false;
  }      
};

class System; 

// This is stored in an thing, and is pointed to by the compiled code
enum CompileLogInfo {
  COMPILE_LOG_ACTION,
  COMPILE_LOG_CODE,
  COMPILE_LOG_INSTRUCTION,
  COMPILE_LOG_INFO_SIZE,
};

enum CompileLogAction {
  COMPILE_ENTER,
  COMPILE_EXIT,
};

struct Vinterpreter;

struct CompileLogger {
  CompileLogger(Vinterpreter * v, Thing code);
  ~CompileLogger();

  Vinterpreter *v_;
  Thing code_;
};

// Do a bunch of things that get interpretation working
void InitInterpret();

struct GlobalInterpreter : public AllocatorDependant {
  GlobalInterpreter() { G_ALLOC->AddDependant(this); }

  // maps from symbols to values
  hash_map<Thing, Thing, ThingHash> globals_;
  
  int32 NumShards() { return 1;}
  void FlagReferences(int32 shard, Frontier *frontier) {
    forall(run, globals_) 
      frontier->Add(run->second); }
  void NotifyDeleted(int32 shard) { }
};
extern GlobalInterpreter * G_INTERP;

struct Vinterpreter {
  ThreadAllocator *a_;
  System * system_;
  Thing * stack_;
  Thing * stack_top_;
  Thing * stack_limit_;
  Thing * debug_stack_;
  Thing * debug_stack_top_;
  Thing * debug_stack_limit_;
  CodeStackFrame * code_stack_;
  CodeStackFrame * code_stack_top_;
  CodeStackFrame * code_stack_limit_;
  HandlerFrame * handler_stack_;
  HandlerFrame * handler_stack_top_;
  HandlerFrame * handler_stack_limit_;
  StableVector<Thing > array_stack_;
  string failure_string_;
  int64 debug_level_;
  RNG rng_;
  Clock clock_;
  int64 clock_check_;
  int64 optimization_depth_;
  Clock wall_clock_;
  set<string> loaded_files_;
  bool safe_execute_die_;
  int64 compile_depth_;
  // used to keep track of the compile depth
  struct CompileFrame {
    CompileFrame(Vinterpreter *vi) {
      vi_ = vi;
      vi_->compile_depth_++;
    }
    ~CompileFrame() {
      vi_->compile_depth_--;
    }     
    Vinterpreter *vi_;
  };

  // Used during compilation
  StableVector<Thing > compile_;
  StableVector<Thing > compile_log_;
  StableVector<pair<Thing , int> > locals_;

  // cache of G_INTERP.globals_
  hash_map<Thing, Thing, ThingHash > globals_;

  // run based global
  Thing run_global_;

  // the system mode this is a power of 2
  // aligns with masks for that mode in the permissions for system calls
  uint64 mode_;

  // Members relating to execution
  const Thing *ip_;
  int64 function_uncachable_count_;
  int64 program_uncachable_count_;
  
  void LoadFile(string fn, bool verbose, uint64 mode);

  void ExecuteStream(istream &input, bool verbose, uint64 mode);

  void PrintHandlerStack();
  void PrintStack();

  // These functions are related to exceptions and time limits

  // Save and restore the current state into an InterpreterState
  void SaveState(InterpreterState * state);
  void RestoreState(const InterpreterState & state);

  // Either call CatchWithHandler or Debug
  void Throw(Thing x, string message);

  // Call when you fail a time limit, calls CatchWithHandler
  void FailTimeLimit(); 

  // Calls Rollback and returns NIL on the stack
  // throw SafeExecuteException if called on a SAFEEXECUTE frame
  void CatchWithHandler(HandlerFrame *p);

  // Go back to a handler frame and restore the interpreter state
  void RollBackHandlerStack(HandlerFrame *p);

  // Add and remove handlers
  void PushHandlerFrame(int64 clock_limit, 
			Thing exceptions, 
			Thing type);
  void PopHandlerFrame() { handler_stack_top_--; }

  // returns success
  bool SetGlobal(Thing key, Thing value);

  // returns NULL on failure
  Thing GetGlobal(Thing key) {
    Thing * look2 = G_INTERP->globals_ % key; 
    if (look2) return *look2; return NULL;
    Thing * look = globals_ % key;    
    if (look) return *look;
    pthread_mutex_lock(&G_LOCK);
    look = G_INTERP->globals_ % key;
    pthread_mutex_unlock(&G_LOCK);
    if (!look) return NULL;
    globals_[key] = *look;
    return *look;
  }

  // instructions until the next limit
  int64 TimeRemaining();
  bool Overtime() { return TimeRemaining() <= 0; }
  bool SometimesOvertime() {
    clock_check_++;
    if ((clock_check_ & 0x7f) == 0) 
      return TimeRemaining() <= 0;
    return false;
  }

  void JumpTo(const Thing *new_ip) { ip_ = new_ip; }
  void JumpBy(int64 distance) { ip_ += distance; }

  // Accessing parameters from the outside
  Thing & GetParameter(int32 i, int32 num) { return stack_top_[i-num]; }
  Thing StackTopToArray(int32 n);
  Thing StackTopToMArray(int32 n);

  Vinterpreter();

  // Simple changes to code
  Thing LambdadCode(Thing& code);
  Thing EvaledCode(Thing & code);

  // Figures out if any code is always constant valued
  // If so, returns the Thing that is its value
  Thing ConstantValue(Thing code);

  // returns an array Thing that cannot be moved.
  Thing CompileWithExit(Thing & code);

  Thing CompileFunction(Thing & code, bool inlining);

  Thing CompileFunctionFast(Thing & code) {
    uint64 cache_key = Fingerprint(code.ID(), 0x29038484093ll);
    Thing cached_val = 0;
    if (a_->cache_.Lookup(cache_key, (uint64 *)(&cached_val) ))
      return cached_val;
    return 0; }

  // return -1000000 if it's not a local symbol
  int LocalSymbolPosition(Thing symbol) {
    int32  pos = -1000000;
    int32 locals_size = locals_.size();
    for (int32 i=0; i<locals_size; i++) {
      int32 index = locals_size - i - 1;
      if (locals_[index].first == symbol) {
	pos = locals_[index].second;
	break;
      }
    }
    return pos;
  }

  // Appends compiled code to compilation.
  // Returns true on success, false on error. 
  // stack_above_params = how many things are above the passed in parameters
  // max_lookback gets set to how many passed in parameters you do look at.  
  // dotimes_indices = the positions in the stack of the indices of dotimes
  //  calls, respresented as distances above the passed parameters.  
  //  dotimes_indices[0] refers to the outermost dotimes, even though in our
  //  programming language, I0 refers to the innermost dotimes. 
  bool Compile(Thing code, int stack_above_frame);
  void Display();

  struct SafeExecuteException{};

  Thing Execute(const Thing *ip_in);
  void ProcessFuncallOp(OpCodes op);
  void ClearStacks();

  Thing SafeExecute(Thing code_in, int64 limit, uint64 mode, Thing exceptions);

  void Debug();
  void DebugFrame(const Thing *ip, Thing compiled_code);
  void DebugParameters(Thing * function_in_stack, 
		       Thing **debug_stack_top);

  // Call this whenever you take an action that causes
  // a function to be uncachable
  void NoFunctionCache() { function_uncachable_count_++; }

  // Did you call something not allowed in generative mode
  void NoProgramCache() {
    // Check for debugging purposes
    // CHECK(mode_ != kGenerativeMode); 
    program_uncachable_count_++;
  }

  // For decompiling
  static map<int , string> op_string_;
};

struct StateSaver {
  HandlerFrame * old_frame_;
  Vinterpreter * vi_;
  StateSaver(Vinterpreter *vi)
  : vi_(vi) { old_frame_ = vi_->handler_stack_top_; }
  ~StateSaver() {
    vi_->RollBackHandlerStack(old_frame_);
  }
};

class System {
 public:
  virtual Thing SystemCall (int32 which, int32 num_parameters) = 0;
  virtual ~System(){}
  virtual void ForgetSince(int64 old_clock) {}
};

int interpret_main();

#endif
